package com.wdc.list_;

@SuppressWarnings({"all"})
public class E01Leetcode234 {
    public static void main(String[] args) {

    }

    public boolean isPalindrome(ListNode head) {

        //1. 翻转链表到中间点
        ListNode middle = middle(head);
        //2、翻转中间链表
        ListNode reverse = reverse(middle);

        //3. 让翻转后的newList 与原始链表中间点前面比较是否相等
        while (reverse != null){
            if (reverse.val != head.val){
                return false;
            }
            reverse = reverse.next;
            head = head.next;
        }

        return true;

    }

    /**
     * 使用快慢指针 找出链表的中间结点并返回中间结点以后的元素
     * @param head 链表的头节点
     * @return  返回中间结点
     */
    public ListNode middle(ListNode head){
        ListNode p1 = head;
        ListNode p2 = head;
        p1 = p1.next;
        p2 = p2.next.next;
        return p1;
    }


    /**
     * 翻转后面一半的元素
     * @param o1
     * @return
     */
    public ListNode reverse(ListNode o1){
        ListNode n1 = null; //翻转后的链表
        while(o1.next != null){
            //记录老二的位置，以便来更新头结点
            ListNode o2 = o1.next;
            //指向新链表头结点
            o1.next = n1;
            //更新头结点
            n1 = o1;
            o2 = o1;

        }
        return n1;
    }


}
